package com.wzh.test;

/**
 * 查找算法
 * 1、顺序查找
 * 2、二分法查找
 * 3、插值查找
 * 4、斐波那契查找
 * 5、树表查找
 * 6、分块查找
 * 7、哈希查找
 */
public class search {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        int index = -2;
        //int index = sequenceSearch(arr,6);
        //index = bianrySearch(arr, 10, 0, arr.length - 1);
        index = insertSearch(arr, 7, 0, arr.length - 1);
        System.out.println(index);
    }

    public static int insertSearch(int[] arr, int value, int left, int right) {
        System.out.println("insertSearch");
        if (left < 0 || right >= arr.length) {
            return -1;
        }
        int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);

        if (value < arr[mid]) {
            return insertSearch(arr, value, left, mid - 1);
        } else if (value > arr[mid]) {
            return insertSearch(arr, value, mid + 1, right);
        } else {
            return mid;
        }
    }

    public static int bianrySearch(int[] arr, int value, int left, int right) {
        System.out.println("bianrySearch");
        if (left < 0 || right >= arr.length) {
            return -1;
        }
        int mid = (left + right) / 2;

        if (value < arr[mid]) {
            return bianrySearch(arr, value, left, mid - 1);
        } else if (value > arr[mid]) {
            return bianrySearch(arr, value, mid + 1, right);
        } else {
            return mid;
        }
    }

    public static int sequenceSearch(int[] arr, int value) {
        int index = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value) {
                index = i;
                break;
            }
        }
        return index;
    }
}
